/**
 * 求[0,N]之间的二进制表示是回文的数量
 * 
 * 仍然从高到低填充，但是注意终止位置不是-1
 * 因为高位填了以后，对应的低位自然就填好了，不能再进行搜索
 * 
 * 因此传入一个名为already的参数，记录已经填充的长度，
 * 当 pos < already 时就需要终止
 * 
 * 其次需要记录低位填充的数字段是否超过了原目标数
 * 注意，这并不是一个剪枝条件，而是需要最后综合考虑
 * 
 * 如果高位始终是贴着目标进行，即limit为真的话，
 * 则低位数字段不能超过原目标数，否则可以超过
 * 
 * 另外注意，该参数以整个低位数字段作为考虑，而非只考虑一位
 * 例如，假设目标数是  10xxxx10
 * 当最高位填1时，最低位也要填1，此时比目标数大，因此该参数记作true
 * 但是当次高位填0时，次低位也要填0，于是此时参数被设置为false
 */

// #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
#else
#define printf _null_func_
#endif

void _null_func_(...){}

using llt = long long;
const llt MOD = 1E9 + 7;

int const FULL = 2; // 2进制
vector<int> G;
llt D[70][70][2];
int Total;
int Dest;

// already表示已填充长度
// largerInLow表示低一半填充的值已经比目标要大，表明高一半不能贴着limit进行
llt dfs(int pos, int already, int largerInLow, bool lead, bool limit){
    printf("dfs(pos=%d,already=%d,largerInLow=%d,lead=%d,limit=%d)\n",pos,already,largerInLow,lead,limit);
    if(pos < already){
        printf("return %d;\n", limit and largerInLow ? 0 : 1);
        return limit and largerInLow ? 0 : 1;
    }
    if(not lead and not limit and -1 != D[pos][already][largerInLow]){
        printf("return D[pos][already][largerInLow] = %lld;\n", D[pos][already][largerInLow]);
        return D[pos][already][largerInLow];
    }

    int last = limit ? G[pos] : FULL - 1;
    llt ans = 0;
    for(int i=0;i<=last;++i){
        printf("Loop: %d, dfs(pos=%d,already=%d,largerInLow=%d,lead=%d,limit=%d)\n",i,pos,already,largerInLow,lead,limit);
        if(i == 0 and lead){
            ans += dfs(pos - 1, 0, 0, true, limit&&last==i);
        }else{
            // 否则要取出对称位置
            int duicheng = already;
            int bitInLowHalf = G[duicheng];
            // 确定新的largerInLow，三种可能
            int nLarger = 0;
            if(bitInLowHalf < i) nLarger = 1; // 显然比原数要大
            else if(bitInLowHalf == i) nLarger = largerInLow; // 显然与参数保持一致
            else ; // do nothing, 为0, 即使之前有Larger现在也要取消
            ans += dfs(pos - 1, already + 1, nLarger, false, limit&&last==i);
        }
    }
    if(not lead and not limit){
        D[pos][already][largerInLow] = ans;
    }
    printf("return ans = %lld;\n", ans);
    return ans;
}

llt digitDP(llt n){
    G.clear();
    while(n){
        G.emplace_back(n & 1);
        n >>= 1;
    }
    Dest = (Total = G.size()) / 2;
    auto tmp = dfs(G.size() - 1, 0, 0, true, true);
    return tmp;
}

class Solution {
public:

    int countBinaryPalindromes(llt n) {
        if(0 == n) return 1;
        memset(D, -1, sizeof(D));

        return digitDP(n);
    }
};